package com.atcumt.Write.sort;

import java.util.Arrays;

/**
 * 堆排序
 * 1.将待排序序列构造成一个大顶堆
 * 2.将堆顶元素和末尾元素交换，将最大元素 "沉" 到数组末端
 * 3.重新调结构，使其满足堆定义，然后继续交换堆顶元素和当前末尾元素
 * 4.反复执行 "调整 + 交换" 直到数组有序
 */
public class HeapSort {

    public static void main(String[] args) {

        int[] arr = new int[] {4, 6, 8, 5, 9};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    /**
     *
     * @param arr 待调整的堆
     * @param parentIndex 要下沉的父节点
     * @param length 堆的有效大小
     */
    private static void maxHeap (int[] arr, int parentIndex, int length) {

        int temp = arr[parentIndex];
        int childIndex = 2 * parentIndex + 1;
        while (childIndex < length) {
            // 如果有右孩子，且值大于左孩子，定位到右孩子
            if (childIndex + 1 < length && arr[childIndex + 1 ] > arr[childIndex]) {
                childIndex++;
            }

            // 如果父节点大于任何一个孩子的值
            if (temp >= arr[childIndex]) {
                break;
            }

            // 无需真正交换，单向赋值！
            arr[parentIndex] = arr[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * childIndex + 1;
        }
        arr[parentIndex] = temp;
    }

    private static void heapSort (int[] arr) {
        // 1.把无序数组构造成最大堆
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            maxHeap(arr, i, arr.length);
        }
        System.out.println(Arrays.toString(arr));

        // 2.循环删除堆顶元素，移到集合尾部，调整堆新产生的堆顶
        for (int i = arr.length - 1; i > 0; i--) {
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;

            maxHeap(arr, 0, i);
        }
    }
}
